package com.zj.study;

public class 最长回文子串_动态规划 {

    public static void main(String[] args) {
        System.out.println(longestPalindrome2("cbbdbbabbd"));
    }


    public static String longestPalindrome(String s) {
        int[] state = new int[s.length() + 1];
        int maxLen = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {//中点
            for (int j = 1; j <= s.length(); j++) {//长度
                int left = i - (j - 1) / 2;
                int right = i + j / 2;
                if (j == 1) {
                    state[j] = 1;
                }

                if (left >= 0 && right < s.length() && j > 1) {
                    int add = s.charAt(left) == s.charAt(right) ? 2 : 0;
                    state[j] = state[j - 2] == (j - 2) ? state[j - 2] + add : state[j - 2];
                }
                if (state[j] > maxLen) {
                    maxLen = state[j];
                    start = left;
                }
            }
        }
        return maxLen >= 1 ? s.substring(start, start + maxLen) : "-1";
    }


    public static String longestPalindrome2(String s) {
        int[] state = new int[s.length() + 1];
        int maxLen = 0;
        int start = 0;
        for (int i = 1; i <= s.length(); i++) {//长度
            for (int j = 0; j < s.length(); j++) {//中心
                int left = j - (i - 1) / 2;
                int right = j + i / 2;
                if (i == 1) {
                    state[i] = 1;
                }

                if (left >= 0 && right < s.length() && i > 1) {
                    int add = s.charAt(left) == s.charAt(right) ? 2 : 0;
                    state[i] = state[i - 2] == (i - 2) ? state[i - 2] + add : state[i - 2];
                }
                if (state[i] > maxLen) {
                    maxLen = state[i];
                    start = left;
                }
            }
        }
        return maxLen >= 1 ? s.substring(start, start + maxLen) : "-1";
    }


}
